The fast Fourier transform (FFT) allows discrete samples of a signal to be transformed from the time domain to the frequency domain. The similar inverse fast Fourier transform (IFFT) transforms from the frequency domain to the time domain. FFT and IFFT are indispensable algorithms for digital signal processing in applications such as certain modems.
The calculation of an FFT is a complicated operation. An application may devote a significant portion of resources such as chip area and power consumption to calculation of an FFT. There is a general need for improvements to the FFT calculation that reduce resource consumption.
The present invention may address one or more of the above issues.